package cn.xkai.exercise.b;

import com.google.gson.Gson;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @description: 图像渲染(传染)
 * @author: kaixiang
 * @date: 2022-07-22
 **/
public class Solution86 {

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] != color) {
            bfs(image, sr, sc, color, image[sr][sc]);
        }
        return image;
    }

    private void dfs(int[][] grid, int i, int j, int newColor, int oldColor) {
        //边界条件判断，不能越界
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != oldColor)
            return;
        //把当前格子置为0，然后再从他的上下左右4个方向继续遍历
        grid[i][j] = newColor;
        //上
        dfs(grid, i - 1, j, newColor, oldColor);
        //下
        dfs(grid, i + 1, j, newColor, oldColor);
        //左
        dfs(grid, i, j + 1, newColor, oldColor);
        //右
        dfs(grid, i, j - 1, newColor, oldColor);
    }

    private void bfs(int[][] grid, int x, int y, int newColor, int oldColor) {
        //把当前格子先置为新值
        grid[x][y] = newColor;
        int n = grid.length;
        int m = grid[0].length;
        //使用队列，存储的是格子坐标转化的值
        Queue<Integer> queue = new LinkedList<>();
        //我们知道平面坐标是两位数字，但队列中存储的是一位数字，
        //所以这里是把两位数字转化为一位数字
        int code = x * m + y;
        //坐标转化的值存放到队列中
        queue.add(code);
        while (!queue.isEmpty()) {
            //出队
            code = queue.poll();
            //在反转成坐标值（i，j）
            int i = code / m;
            int j = code % m;
            //上
            if (i > 0 && grid[i - 1][j] == oldColor) {
                grid[i - 1][j] = newColor;
                queue.add((i - 1) * m + j);
            }
            //下
            if (i < n - 1 && grid[i + 1][j] == oldColor) {
                grid[i + 1][j] = newColor;
                queue.add((i + 1) * m + j);
            }
            //左
            if (j > 0 && grid[i][j - 1] == oldColor) {
                grid[i][j - 1] = newColor;
                queue.add(i * m + j - 1);
            }
            //右
            if (j < m - 1 && grid[i][j + 1] == oldColor) {
                grid[i][j + 1] = newColor;
                queue.add(i * m + j + 1);
            }
        }
    }

    public static void main(String[] args) {
        int[][] image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        int[][] image1 = {{0, 0, 0}, {0, 0, 0}};
        int sr = 0, sc = 0, newColor = 0;
        Solution86 solution86 = new Solution86();
        System.out.println(new Gson().toJson(solution86.floodFill(image1, sr, sc, newColor)));
    }
}

